class Solution(object):
    def findRightInterval(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[int]
        """
        n = len(intervals)
        out = [-1] * n
        start = [[intervals[i][0], i] for i in range(n)]
        end = [[intervals[i][1], i] for i in range(n)]
        start.sort()
        end.sort()
        end_index = 0
        start_index = 0
        while start_index < n:
            if start[start_index][0] < end[end_index][0]:
                start_index += 1
            else:
                while end_index < n and start[start_index][0] >= end[end_index][0]:
                    out[end[end_index][1]] = start[start_index][1]
                    end_index += 1
                start_index += 1
        return out





data = Solution()
intervals = [[3, 4], [2, 3], [1, 2]]
print(data.findRightInterval(intervals))
intervals = [[1, 4], [2, 3], [3, 4]]
print(data.findRightInterval(intervals))
